using System;

namespace Com.FirstSolver.Splash;

public class FpFieldElement : ECFieldElement
{
	private readonly BigInteger q;

	private readonly BigInteger x;

	public override string FieldName => "Fp";

	public override int FieldSize => q.BitLength;

	public BigInteger Q => q;

	public FpFieldElement(BigInteger q, BigInteger x)
	{
		if (x.CompareTo(q) >= 0)
		{
			throw new ArgumentException("x value too large in field element");
		}
		this.q = q;
		this.x = x;
	}

	public override BigInteger ToBigInteger()
	{
		return x;
	}

	public override byte[] GetEncoded()
	{
		int FieldSizeInBytes = q.BitLength + 7 >> 3;
		byte[] bytes = x.ToByteArrayUnsigned();
		if (bytes.Length > FieldSizeInBytes)
		{
			byte[] tmp = new byte[FieldSizeInBytes];
			Array.Copy(bytes, bytes.Length - FieldSizeInBytes, tmp, 0, FieldSizeInBytes);
			return tmp;
		}
		if (bytes.Length < FieldSizeInBytes)
		{
			byte[] tmp2 = new byte[FieldSizeInBytes];
			Array.Copy(bytes, 0, tmp2, FieldSizeInBytes - bytes.Length, bytes.Length);
			return tmp2;
		}
		return bytes;
	}

	public override ECFieldElement Add(ECFieldElement b)
	{
		return new FpFieldElement(q, x.Add(b.ToBigInteger()).Mod(q));
	}

	public override ECFieldElement Subtract(ECFieldElement b)
	{
		return new FpFieldElement(q, x.Subtract(b.ToBigInteger()).Mod(q));
	}

	public override ECFieldElement Multiply(ECFieldElement b)
	{
		return new FpFieldElement(q, x.Multiply(b.ToBigInteger()).Mod(q));
	}

	public override ECFieldElement Divide(ECFieldElement b)
	{
		return new FpFieldElement(q, x.Multiply(b.ToBigInteger().ModInverse(q)).Mod(q));
	}

	public override ECFieldElement Negate()
	{
		return new FpFieldElement(q, x.Negate().Mod(q));
	}

	public override ECFieldElement Square()
	{
		return new FpFieldElement(q, x.Multiply(x).Mod(q));
	}

	public override ECFieldElement Invert()
	{
		return new FpFieldElement(q, x.ModInverse(q));
	}

	public override ECFieldElement Sqrt()
	{
		if (!q.TestBit(0))
		{
			throw new NotImplementedException("even value of q");
		}
		if (q.TestBit(1))
		{
			ECFieldElement z = new FpFieldElement(q, x.ModPow(q.ShiftRight(2).Add(BigInteger.One), q));
			return z.Square().Equals(this) ? z : null;
		}
		BigInteger u = q.ShiftRight(3);
		if (q.TestBit(2))
		{
			BigInteger z2 = x.ModPow(u.ShiftLeft(1).Add(BigInteger.One), q);
			if (z2.Equals(BigInteger.One))
			{
				return new FpFieldElement(q, x.ModPow(u.Add(BigInteger.One), q));
			}
			if (z2.Equals(q.Subtract(BigInteger.One)))
			{
				return new FpFieldElement(q, x.ShiftLeft(1).Multiply(x.ShiftLeft(2).ModPow(u, q)).Mod(q));
			}
			return null;
		}
		BigInteger qMinusOne = q.Subtract(BigInteger.One);
		BigInteger legendreExponent = qMinusOne.ShiftRight(1);
		if (!x.ModPow(legendreExponent, q).Equals(BigInteger.One))
		{
			return null;
		}
		BigInteger i = legendreExponent.Add(BigInteger.One);
		BigInteger fourY = x.ShiftLeft(2).Mod(q);
		Random rand = new Random();
		while (true)
		{
			BigInteger r = new BigInteger(q.BitLength, rand);
			if (r.CompareTo(q) >= 0 || !r.Multiply(r).Subtract(fourY).ModPow(legendreExponent, q)
				.Equals(qMinusOne))
			{
				continue;
			}
			BigInteger[] result = LucasSequence(q, r, x, i);
			BigInteger U = result[0];
			BigInteger V = result[1];
			if (V.Multiply(V).Mod(q).Equals(fourY))
			{
				if (V.TestBit(0))
				{
					V = V.Add(q);
				}
				return new FpFieldElement(q, V.ShiftRight(1).Mod(q));
			}
			if (!U.Equals(BigInteger.One) && !U.Equals(qMinusOne))
			{
				break;
			}
		}
		return null;
	}

	private static BigInteger[] LucasSequence(BigInteger p, BigInteger X, BigInteger Y, BigInteger k)
	{
		int l = k.BitLength;
		int s = k.GetLowestSetBit();
		BigInteger D = X.Multiply(X).Subtract(Y.ShiftLeft(2));
		BigInteger U = BigInteger.One;
		BigInteger V = X;
		for (int j = l - 1; j >= s; j--)
		{
			if (k.TestBit(j))
			{
				BigInteger T = X.Multiply(U).Add(V).ShiftRight(1)
					.Mod(p);
				V = X.Multiply(V).Add(D.Multiply(U)).ShiftRight(1)
					.Mod(p);
				U = T;
			}
			else
			{
				BigInteger T = U.Multiply(V).Mod(p);
				V = V.Multiply(V).Add(D.Multiply(U.Multiply(U))).ShiftRight(1)
					.Mod(p);
				U = T;
			}
		}
		for (int i = 1; i <= s; i++)
		{
			BigInteger T = U.Multiply(V).Mod(p);
			V = V.Multiply(V).Add(D.Multiply(U.Multiply(U))).ShiftRight(1)
				.Mod(p);
			U = T;
		}
		return new BigInteger[2] { U, V };
	}

	public override bool Equals(object obj)
	{
		if (obj == this)
		{
			return true;
		}
		if (!(obj is FpFieldElement other))
		{
			return false;
		}
		return Equals(other);
	}

	protected bool Equals(FpFieldElement other)
	{
		return q.Equals(other.q) && Equals((ECFieldElement)other);
	}

	public override int GetHashCode()
	{
		return q.GetHashCode() ^ base.GetHashCode();
	}
}
